#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        long long res = 0;
        unordered_map<int, int> maps1;
        unordered_map<int, int> maps2;
        int n = nums1.size(), m = nums2.size();
        int max1 = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums1[i] % k == 0)
            {
                maps1[nums1[i] / k]++;
                max1 = max(max1, nums1[i] / k);
            }
        }
        for (int i = 0; i < m; i++)
        {
            maps2[nums2[i]]++;
        }

        for (auto pair2 : maps2)
        {
            long long num = pair2.first, cnt = pair2.second;
            for (int i = num; i <= max1; i += num)
            {
                if (maps1.count(i) > 0) res += cnt * maps1[i];
            }
        }
        return res;
    }
};